/**
 * 
 */
package backtrack.passed2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @author xyyi
 *
 */
public class Permutation {

    /**
    Permutations
    Given a collection of numbers, return all possible permutations.

    For example,
    [1,2,3] have the following permutations:
    [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
     */
    public List<List<Integer>> permuteR1(int[] num) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        if (num != null && num.length != 0)
        	permuteR1Helper(num, 0, list);
        return list;
    }

    public void permuteR1Helper(int[] num, int index, List<List<Integer>> list) {
        if (num.length == index) {
            List<Integer> buffer = new ArrayList<Integer>(num.length);
            for (int i = 0; i < num.length; i++) {
                buffer.add(num[i]);
            }
            list.add(buffer);
        } else {
            for (int i = index; i < num.length; i++) {
                swap(num, i, index);
                permuteR1Helper(num, index + 1, list);
                swap(num, i, index);
            }
        }
    }
    
    // swap
    public List<List<Integer>> permuteR0(int[] num) {
        List<List<Integer>> permutations = new ArrayList<List<Integer>>();
        if (num != null && num.length != 0) {
            List<Integer> numList = new ArrayList<Integer>(num.length);
            for (int i : num)
                numList.add(i);
            permuteR0Helper(numList, 0, permutations);
        }
        return permutations;
    }

    private void permuteR0Helper(List<Integer> numList, int index, List<List<Integer>> permutations) {
        if (numList.size() - 1 == index) {
            permutations.add(new ArrayList<>(numList));
        } else {
            for (int i = index; i < numList.size(); i++) {
                Collections.swap(numList, i, index);
                permuteR0Helper(new ArrayList<>(numList), index + 1, permutations);
            }
        }
    }// 
    

    // Good for interview
    public List<List<Integer>> permuteR2(int[] num) {
        List<List<Integer>> permutations = new ArrayList<List<Integer>>();
        if (num != null && num.length != 0) {
            boolean[] visited = new boolean[num.length];
            permuteR2Helper(num, visited, permutations, new ArrayList<Integer>());
        }
        return permutations;
    }

    private void permuteR2Helper(int[] num, boolean[] visited,
            List<List<Integer>> permutations, List<Integer> cache) {
        if (cache.size() == num.length) {
        	permutations.add(new ArrayList<Integer>(cache));
        } else {
            for (int i = 0; i < num.length; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    cache.add(num[i]);
                    permuteR2Helper(num, visited, permutations, cache);
                    cache.remove(cache.size() - 1);
                    visited[i] = false;
                }
            }
        }
    }// R
    
    public List<List<Integer>> permuteI(int[] num) {
        List<List<Integer>> permutations = new LinkedList<List<Integer>>();
        if (num == null || num.length == 0) {
            return permutations;
        }
//		Arrays.sort(num);
        permutations.add(new LinkedList<Integer>());
        
        for (int i = 0; i < num.length; i++) {
            List<List<Integer>> cache = new LinkedList<List<Integer>>();
            for (List<Integer> permutation : permutations) {
                for (int j = 0; j <= permutation.size(); j++) {
                    List<Integer> newPermutation = new LinkedList<Integer>(permutation);
                    newPermutation.add(j, num[i]);
                    cache.add(newPermutation);
                }
            }
            permutations = cache;
        }
        
        return permutations;
    }

    /**
    Permutations II
    Given a collection of numbers that might contain duplicates, return all possible unique permutations.

    For example,
    [1,1,2] have the following unique permutations:
    [1,1,2], [1,2,1], and [2,1,1].
     */
    // good for interview
    public List<List<Integer>> permuteUniqueR(int[] num) {
        List<List<Integer>> permutations = new LinkedList<List<Integer>>();
        if (num != null && num.length > 0) {
            Arrays.sort(num);
            permuteUniqueRHelper(num, new boolean[num.length], new ArrayList<Integer>(), permutations);
        }
        return permutations;
    }
    
    private void permuteUniqueRHelper(int[] num, boolean[] selected, List<Integer> cache, List<List<Integer>> permutations) {
        if (cache.size() == num.length) {
            permutations.add(new LinkedList<>(cache));
        }
        else {
            for (int i = 0; i < num.length; i++) {
                if (selected[i] || i > 0 && num[i] == num[i - 1] && !selected[i - 1])
                    continue;
                selected[i] = true;
                cache.add(num[i]);
                permuteUniqueRHelper(num, selected, cache, permutations);
                selected[i] = false;
                cache.remove(cache.size() - 1);
            }
        }
    }
    
    // swap
    public List<List<Integer>> permuteUniqueR0(int[] num) {
        List<List<Integer>> permutations = new ArrayList<List<Integer>>();
        if (num != null && num.length != 0) {
            List<Integer> numList = new ArrayList<Integer>(num.length);
            for (int i : num)
                numList.add(i);
            permuteUniqueR0Helper(numList, 0, permutations);
        }
        return permutations;
    }

    private void permuteUniqueR0Helper(List<Integer> numList, int index, List<List<Integer>> permutations) {
        if (numList.size() - 1 == index) {
            permutations.add(new ArrayList<>(numList));
        } else {
            for (int i = index; i < numList.size(); i++) {
            	if (i != index && numList.get(i) == numList.get(index))
            		continue;
            	Collections.swap(numList, i, index);
            	permuteUniqueR0Helper(new ArrayList<>(numList), index + 1, permutations);
            }
        }
    }//
    
    public List<List<Integer>> permuteUniqueI(int[] num) {
    	return null;
    }

    // FAIL to pass leetcode
    public ArrayList<ArrayList<Integer>> permuteUniqueRFail(int[] num) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0)
            return list;

        Arrays.sort(num);// may need to create a new array
        permuteUniqueRFailHelper(num, 0, list);
        return list;
    }
    
    private void permuteUniqueRFailHelper(int[] num, int index,
            ArrayList<ArrayList<Integer>> list) {
        if (num.length == index) {
            ArrayList<Integer> buffer = new ArrayList<Integer>(num.length);
            for (int i = 0; i < num.length; i++) {
                buffer.add(num[i]);
            }
            list.add(buffer);
        } else {
            for (int i = index; i < num.length; i++) {
                if (i != index
                        && (num[i] == num[index] || num[i] == num[i - 1])) {
                    continue;
                }
                swap(num, i, index);
                permuteUniqueRFailHelper(num, index + 1, list);
                swap(num, i, index);
            }
        }
    }// FAIL to pass leetcode

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }// FAIL to pass leetcode
    
    /**
     * 
     */
    public Permutation() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Permutation p = new Permutation();

//        int[] num = { 0, 1, 0, 0, 9 };
//        int[] num = {2,2,1,1};
        int[] num = {1, 2, 3};
        List<List<Integer>> result1 = p.permuteR0(num);
        p.print(result1);
    }

    public void printDulipcate(ArrayList<ArrayList<Integer>> result) {
        System.out.printf("Total: %d\n", result.size());
        HashSet<ArrayList<Integer>> hash = new HashSet<ArrayList<Integer>>();
        for (ArrayList<Integer> arr : result) {
            if (hash.contains(arr)) {
                for (Integer i : arr) {
                    System.out.printf("%d,", i);
                }
                System.out.println();
            } else {
                hash.add(arr);
            }
        }

        System.out.println();
    }

    private void printSpace(int n) {
    	for (int i = 0; i < n; i++) {
    		System.out.printf("-");
    	}
    }
    
    
    private void printList(List<Integer> list) {
    	for (int i : list) {
    		System.out.printf("%d,", i);
    	}
    	System.out.println();
    }
    
    private void print(List<List<Integer>> result) {
        System.out.printf("Total: %d\n", result.size());
        for (List<Integer> arr : result) {
            for (Integer i : arr) {
                System.out.printf("%d,", i);
            }
            System.out.println();
        }
    }
}
